package com.cuz.daileetcode.utils.graph;

import com.cuz.daileetcode.Day34;

import java.util.*;
import java.util.function.Consumer;
import java.util.function.Predicate;

/**
 * @author cuzz
 * @version 1.0
 * @description: 图 存储节点和边
 * @date 22:01 2021/12/8
 **/
public class Graph<T> {

    /***
     * 节点值 指向节点本身 记录所有的节点
     */
    public HashMap<T, Node<T>> nodes;
    /***
     * 存储此图的所有边
     */
    public HashSet<Edge<T>> edges;

    /***
     * 初始化一张图
     * @param <T>
     * @return 图
     */
    public static <T> Graph<T> create() {
        Graph<T> instance = new Graph<>();
        instance.edges = new HashSet<>();
        instance.nodes = new HashMap<>();
        return instance;
    }

    /****
     * 图的宽度优先遍历
     * 使队列实现，HashSet避免环
     * @param start 开始节点
     * @param consumer 消费者，你要执行的操作
     */
    public static <T> void bfs(Node<T> start, Consumer<Node<T>> consumer) {
        if (start == null || consumer == null) {
            return;
        }
        //宽度优先遍历 辅助队列
        LinkedList<Node<T>> queue = new LinkedList<>();
        //宽度优先遍历 记忆set 避免重复操作相同的节点，成环的死循环
        HashSet<Node<T>> memory = new HashSet<>();
        //首先假如当前节点
        queue.addLast(start);
        memory.add(start);
        while (!queue.isEmpty()) {
            //移除队列头部节点
            Node<T> curNode = queue.removeFirst();
            //消费
            consumer.accept(curNode);
            //此节点的所有节点
            for (Node<T> nextNode : curNode.nexts) {
                //如果没有遍历到过
                if (!memory.contains(nextNode)) {
                    //加入memory
                    memory.add(nextNode);
                    //放在队列尾
                    queue.addLast(nextNode);
                }
            }
        }
    }

    public static <T> void dfs(Node<T> start, Consumer<Node<T>> consumer) {
        if (start == null || consumer == null) {
            return;
        }
        //深度优先遍历 辅助栈
        Stack<Node<T>> stack = new Stack<>();
        // 记忆set 避免重复操作相同的节点，成环的死循环
        HashSet<Node<T>> memory = new HashSet<>();
        stack.add(start);
        memory.add(start);
        //如果存在元素，
        while (!stack.isEmpty()) {
            //拿到当前节点
            Node<T> curNode = stack.pop();
            //循环遍历所有下一个节点
            for (Node<T> nextNode : curNode.nexts) {
                //如果不包含下一个节点，说明这条路还没走过
                if (!memory.contains(nextNode)) {
                    //把当前节点压栈回去
                    stack.add(curNode);
                    //把下一个节点压入
                    stack.add(nextNode);
                    consumer.accept(curNode);
                    //终止当前循环，下一次循环 拿到的是nextNode
                    //相当于走到nextNode，一条路走到黑 直到无法走下去
                    break;
                }
            }
        }
    }


    /***
     * 拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。
     * 且该序列必须满足下面两个条件：
     * 1.每个顶点出现且只出现一次。
     * 2.若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
     * !!!!有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。
     * @return
     */
    public List<Node<T>> topologicalSort() {
        //每一个点和其对于的入度
        HashMap<Node<T>, Integer> inMap = new HashMap<>();
        //入度为0的点
        Queue<Node<T>> zeroInQueue = new LinkedList<>();
        Collection<Node<T>> allNodeInGraph = this.nodes.values();
        //首先找到初始入度为0的点 可理解为程序包中不依赖于任何节点的节点
        for (Node<T> tempNode : allNodeInGraph) {
            if (tempNode.in == 0) {
                zeroInQueue.add(tempNode);
            }
        }
        List<Node<T>> res = new ArrayList<>();
        while (!zeroInQueue.isEmpty()) {
            //拿出一个入度为0的点，入度为0的点是结果的一份子
            Node<T> curNode = zeroInQueue.poll();
            res.add(curNode);
            //循环遍历 next
            for (Node<T> next : curNode.nexts) {
                //拿到next的入度
                Integer nowIn = inMap.get(next);
                //减1
                nowIn--;
                //重新覆盖
                inMap.put(next, nowIn);
                //如果删除curNode对next的入度影响后 ，入度为0 那么加入到zeroInQueue
                //接下来它的下一个节点也会为减小 相当于小于了next的影响
                if (nowIn == 0) {
                    zeroInQueue.add(next);
                }
            }
        }
        return res;
    }

    public static class SimulationUnionSet<T> {
        public HashMap<Node<T>, List<Node<T>>> memory = new HashMap();

        /***
         * 根据图生成模拟并查集 将每个节点初始化指向自己的单个集合
         * @param graph 图
         */
        public static <T> Day34.SimulationUnionSet<T> create(Graph<T> graph) {
            Day34.SimulationUnionSet<T> res = new Day34.SimulationUnionSet<T>();
            for (Node<T> tempNode : Objects.requireNonNull(graph).nodes.values()) {
                res.memory.put(tempNode, Collections.singletonList(tempNode));
            }
            return res;
        }

        /**
         * 两个节点是否属于同一个集
         *
         * @return
         */
        public boolean isSame(Node<T> node1, Node<T> node2) {
            return memory.get(node1) == memory.get(node2);
        }

        /**
         * 合并
         * 让前者的集合包括后者集合中的每一个元素
         * 并且让后者集合中的每一个节点指向前者集合
         */
        public void union(Node<T> node1, Node<T> node2) {
            if (isSame(node1, node2)) {
                return;
            }
            List<Node<T>> node1List = memory.get(node1);
            List<Node<T>> node2List = memory.get(node2);
            Objects.requireNonNull(node1List);
            Objects.requireNonNull(node2);
            for (Node<T> temNode : node2List) {
                node1List.add(temNode);
                memory.put(temNode, node1List);
            }
        }
    }

    /***
     * kruskal 生成最小生成树
     * @param graph
     * @param <T>
     * @return
     */
    public static <T> Set<Edge<T>> kruskal(Graph<T> graph) {
        Objects.requireNonNull(graph);
        //生成模拟并查集
        Day34.SimulationUnionSet<T> unionSet = Day34.SimulationUnionSet.create(graph);
        //将所有Edge 按照weight排序
        PriorityQueue<Edge<T>> heap = new PriorityQueue<>(Edge.edgeWeightComparator());
        //加入所有edge
        heap.addAll(graph.edges);
        //结果
        Set<Edge<T>> res = new HashSet<>();
        while (!heap.isEmpty()) {
            //拿到当前权重最小的边
            Edge<T> tempEdge = heap.poll();
            Node<T> from = tempEdge.from;
            Node<T> to = tempEdge.to;
            //两个节点是否属于同一个集，如果使代表选择会成环 那么继续下一轮
            //反之加入边，合并两个节点的集合
            if (!unionSet.isSame(from, to)) {
                unionSet.union(from, to);
                res.add(tempEdge);
            }
        }
        return res;
    }

    /***
     * prim算法 贪心
     * 每次拿当前所有能到边的最小权重边加入结果，并且将此边的指向目标加入set，避免无线死循环
     * @return 最小生成树的边
     */
    public Set<Edge<T>> prim() {
        //随机拿一个点
        Node<T> randNode = this.nodes.values().stream()
                .findAny()
                .orElseThrow(() -> new IllegalArgumentException("图不存在节点"));
        //节点memory
        HashSet<Node<T>> nodeMemory = new HashSet<>();
        //结果集合
        HashSet<Edge<T>> res = new HashSet<>();
        nodeMemory.add(randNode);
        //根据edge权重定义的小根堆
        PriorityQueue<Edge<T>> heap = new PriorityQueue<>(Edge.edgeWeightComparator());
        //首先把这个节点的所有边加入进去
        heap.addAll(randNode.edges);
        //如果存在边
        while (!heap.isEmpty()) {
            //拿当前最小的边
            Edge<T> minWeightEdge = heap.poll();
            //最小边的指向
            Node<T> edgePointTo = minWeightEdge.to;
            //如果假如最小边指向节点成功 代表之没这个节点
            if (nodeMemory.add(edgePointTo)) {
                //这个边是我们需要的
                res.add(minWeightEdge);
                //把这个点指向的所有边加入
                heap.addAll(edgePointTo.edges);
            }
        }
        return res;
    }

    /****
     * dijkstra 算法实现从节点start出发找到到每一个节点最短的路径距离
     * @param start 起始节点
     * @return Map<Node<T33>, Integer> 从start开始到每个可达点的距离
     */
    public Map<Node<T>, Integer> dijkstra(Node<T> start) {
        Objects.requireNonNull(start);
        //key 表示从start到key对应node。value：距离Integer
        HashMap<Node<T>, Integer> res = new HashMap<>();
        //初始化 现在相当于表中数据 为A->A距离0
        res.put(start, 0);
        //记录哪些点已经使用过（作为中间过路点使用过了）
        HashSet<Node<T>> memory = new HashSet<>();
        //当前可用到节点中距离最小的节点肯定是自己啊
        Node<T> minDistanceNode = start;
        while (minDistanceNode != null) {
            //最小距离节点有那些边
            List<Edge<T>> allEdgesReach =Optional.ofNullable(minDistanceNode.edges)
                    .orElse(Collections.emptyList());
            //原来到这个最小距离节点有多远、
            //比如当前curDistanceNode为B，sourceDistance 就是A->原来的距离
            Integer sourceDistance = res.get(minDistanceNode);
            //遍历每一个边
            for (Edge<T> eachEdge : allEdgesReach) {
                //这个边可到那个点
                Node<T> targetNode = eachEdge.to;
                //当前边的权重，也就是从最小距离节点到这个点需要多元
                int edgeWeight = eachEdge.weight;
                //这个边目标点在源map中的距离 相当于没更新前的距离，如果为空设置为最大
                Integer targetNodeDistance = res.getOrDefault(targetNode, Integer.MAX_VALUE);
                //更新设置为较小节点
                //fixme 【堆优化 】 使用子实现堆让更新的时候同步进行堆的调整 getMinDistanceNodeBy方法可用从堆中拿
                //fixme 【堆优化 】 堆排序依据：start到堆中节点的距离，使用小根堆
                //fixme 【堆优化 】为什么自实现堆，因为需要改变堆中的数据 java自己的优先队列改变的话时间复杂度提升不高
                res.put(targetNode,Math.min(sourceDistance+edgeWeight,targetNodeDistance));
                //表示这个边已经使用过了
                memory.add(targetNode);
                //更新最小距离节点
                minDistanceNode = getMinDistanceNodeBy(res, tempNode -> !memory.contains(tempNode));
            }
        }
        return res;
    }

    /***
     * 根据当前的距离表，找到一个距离最小的节点
     * @param distanceMap 距离表
     * @param filter 输入你的过滤规则
     * @return 距离最小的点
     */
    private Node<T> getMinDistanceNodeBy(HashMap<Node<T>, Integer> distanceMap, Predicate<Node<T>> filter) {
        Node<T> minDistanceNode = null;
        int minDistance = Integer.MAX_VALUE;
        for (Map.Entry<Node<T>, Integer> entry : distanceMap.entrySet()) {
            Integer distanceOfCurNode = entry.getValue();
            Node<T> curNode = entry.getKey();
            //符合当前条件：1 距离比最小距离minDistance小 2.符合filter 的条件
            if (distanceOfCurNode < minDistance && filter.test(curNode)) {
                minDistance = distanceOfCurNode;
                minDistanceNode = curNode;
            }
        }
        return minDistanceNode;
    }
}
